COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.s(MICRO, A MICRO-MANUAL FOR LISP - MOSTLY TRUTHFUL)
C00013 ENDMK
C⊗;
.s(MICRO, A MICRO-MANUAL FOR LISP - MOSTLY TRUTHFUL)
.BEGIN "MICRO"
.at "z1" ⊂"%41%*"⊃
.at "zn" ⊂"%4n%*"⊃
.ITEM←0
.ss Basic notions.

	LISP data are symbolic expressions that can be either
%2atoms%1 or %2lists%1.  %2Atoms%1 are strings of letters
and digits and other characters not otherwise used in LISP.
A ⊗list consists of a left parenthesis followed by
zero or more atoms or lists separated by spaces and ending with a right parenthesis.
Examples: $$A, ONION, (), (A), (A ONION A), (PLUS A (TIMES B ONION) 1)$.

	The LISP programming language is defined by rules for %2evaluating%1
certain LISP expressions to yield other LISP expressions as their values.
The function ⊗value used in giving these rules is not part of the LISP
language but rather part of the informal language in which LISP is being
defined.  Likewise, the italic letters ⊗e and ⊗a (sometimes with subscripts)
denote LISP expressions, the letter ⊗v (usually subscripted) denotes an
atom serving as a variable, and the letter ⊗f stands for a LISP expression
serving as a function name.

#. ⊗⊗value ($QUOTE e) = e⊗.  For example, the value of $$(QUOTE A)$ is $$A$.

#. ⊗⊗value ($CAR e)⊗, where ⊗⊗value e⊗ is a non-empty list, is the first element
of ⊗⊗value_e⊗.  Thus ⊗⊗value_$$(CAR_(QUOTE_(A_B_C)))$_=_$$A$.

#. ⊗⊗value ($CDR e)⊗, where ⊗⊗value e⊗ is a non-empty list, is the
the list that remains when the first element
of ⊗⊗value_e⊗ is deleted.  Thus ⊗⊗value_$$(CDR (QUOTE (A B C)))$ = $$(B C)$.⊗

#. ⊗⊗value ($CONS e1 e2)⊗, is the list that results from prefixing
⊗⊗value_e1⊗ onto the list ⊗⊗value_e2⊗.  Thus
⊗⊗value_$$(CONS (QUOTE A) (QUOTE (B C)))$ = $$(A B C)$.⊗

#. ⊗⊗value ($EQUAL e1 e2)⊗ is qT if ⊗⊗value e1 = value e2⊗.  Otherwise,
its value is qNIL.  Thus ⊗⊗value_$$(EQUAL_(CAR_(QUOTE_(A_B)))_(QUOTE_A))$_=_qT⊗.

#. ⊗⊗value ($ATOM e) = qT⊗ if ⊗⊗value e⊗ is an atom; otherwise its
value is qNIL. 

#. ⊗⊗value ($COND (pz1 ez1) ... (pzn ezn)) = value e%4i%*⊗,
where ⊗⊗p%4i%*⊗ is the the first of the ⊗⊗p⊗'s whose value is not qNIL.
Thus
⊗⊗value_$$(COND_((ATOM_(QUOTE_A))_(QUOTE_B))_((QUOTE_T)_(QUOTE_C)))$_=_$$B$⊗.

#. An atom ⊗v, regarded as a variable, may have a value.

#. ⊗⊗value (($LAMBDA (vz1 ... vzn) e) ez1 ... ezn)⊗ is
the same as ⊗⊗value_e⊗ but in an environment in which
the variables ⊗⊗vz1_..._vzn⊗ take the values of the
expressions ⊗⊗ez1_..._ezn⊗ in the original environment.  Thus
⊗⊗value_$$((LAMBDA_(X_Y)_(CONS_(CAR_X)_Y))_(QUOTE_(A_B))_(CDR_(QUOTE_(C_D))))$_=_$$(A_D)$⊗.

#. Here's the hard one.  ⊗⊗value (($LABEL f ($LAMBDA (vz1 ... vzn) e))
ez1 ... ezn)⊗ is the same as ⊗⊗value_(($LAMBDA (vz1_..._vzn)_e)_ez1_..._ezn)⊗, 
but whenever ⊗⊗(f_az1 ..._azn)⊗ must be evaluated, ⊗f 
is replaced by ⊗⊗($LABEL f_($LAMBDA (vz1_..._vzn)_e))⊗.  
Lists beginning with $LABEL define functions recursively.

	This is the core of LISP, and here are more examples:

⊗⊗⊗value $$(CAR X)$ = $$(A B)$⊗ if ⊗⊗value $$X$ = $$((A B) C)$⊗, and

⊗⊗⊗value$$((LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X))))))
(QUOTE ((A B) C)))$ = $$A$.⊗

Thus $$((LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X))))))$,
is the LISP name of a function ⊗ff such that ⊗⊗ff_e⊗ is the
first atom in the written form of ⊗e. 
Note that the list ⊗ff is substituted for the atom $FF twice in the course of
evaluating the above expression.

Difficult mathematical type exercise: Find a list ⊗e such that ⊗⊗value e = e⊗.

	You may now program in LISP.  Call LISP system on a
time-sharing computer, type in a list, and LISP will type back its value.

.ss Some Useful Abbreviations.

	The above LISP needs some abbreviations for practical use.
.item←0

#. So as not to describe a LISP function 
each time it is used, we define it permanently by typing
⊗⊗($DEFUN f_(vz1_..._vzn)_e)⊗.  Thereafter
⊗⊗(f_ez1_..._ezn)⊗ is evaluated by evaluating ⊗e with the variables
⊗⊗vz1,_..._,vzn⊗ taking the values ⊗⊗value_ez1,_..._,value_ezn⊗
respectively.  Thus, after we define
$$(DEFUN_FF_(X)_(COND_((ATOM_X)_X)_((QUOTE_T)_(FF_(CAR_X)))))$,
typing  $$(FF_(QUOTE_((A_B)_C)))$, gets $$A$ from LISP.

#. The variables $$T$ and $$NIL$ are permanently assigned the values
$$T$ and $$NIL$, and $$NIL$ is the name of the null list ().  Therefore,
the above definition can be written
$$(DEFUN_FF_(X)_(COND_((ATOM_X)_X)_(T_(FF_(CAR_X)))))$.

#. We have the permanent function definitions

		$$(DEFUN NULL (X) (EQUAL X NIL))$ and $$(DEFUN CADR (X) (CAR (CDR X)))$,

and similarly for arbitrary combinations of $$A$ and $$D$.

#. ⊗⊗($LIST ez1 ... ezn)⊗ is defined for each ⊗n to be
⊗⊗($CONS ez1_($CONS ..._($CONS ezn_qNIL)))⊗.

#. ⊗⊗($AND p q)⊗ abbreviates
⊗⊗($COND (p_q)_(qT_qNIL))⊗.  $$AND$s with more terms are defined
similarly, and the propositional connectives
$$OR$ and $$NOT$ abbreviate similar conditional expressions.

	Now we can give some further examples of LISP function definitions:

$$(DEFUN ALT (X) (COND ((OR (NULL X) (NULL (CDR X))) X) (T (CONS (CAR X)
(ALT (CDDR X))))))$

defines a function that gives alternate elements of a list starting with
the first element.  Thus
$$(ALT_(QUOTE_(A_B_C_D_E)))$_=_$$(A_C_E)$.
.NOFILL

        $$(DEFUN SUBST (X Y Z) (COND ((ATOM Z) (COND ((EQUAL Z Y) X) (T Z)))$
                                       $$(T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z))))))$
.FILL
gives the result of substituting $$X$ for $$Y$ in $$Z$.  Thus

	$$(SUBST (QUOTE (PLUS X Y)) (QUOTE V) (QUOTE (TIMES X V)))$ = $$(TIMES X (PLUS X Y))$.
.END "MICRO"